package com.ibm.rules.test;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Random;
import java.util.TreeSet;

import com.google.common.collect.Range;
import com.google.common.collect.RangeMap;
import com.google.common.collect.TreeRangeMap;

public class BinarySearchTreeNode {
	
	/*
	 * here we suppose range is always format (...]
	 */
	public static class MyRange {
		
		public MyRange(double l, double r, int id) {
			this.leftbd = l;
			this.rightbd = r;
			this.rangeid = id;
		}

		double leftbd;
		double rightbd;
		int rangeid;
		
	}

	/* suppose splitrange is never overlapped */
	public static class SplitRange implements Comparable<SplitRange> {
		double leftbd;
		double rightbd;

		public SplitRange(double lb, double rb) {
			this.leftbd = lb;
			this.rightbd = rb;
		}

		HashSet<Integer> refranges = new HashSet<Integer>();

		@Override
		public int compareTo(SplitRange o) {
			return (int) (leftbd - o.leftbd);
		}

		public void addRange(MyRange r) {
			refranges.add(r.rangeid);
		}
	}

	TreeSet<Double> splitpointset = new TreeSet<Double>();

	public ArrayList<SplitRange> splitrangelist = new ArrayList<BinarySearchTreeNode.SplitRange>();
	/* from rule-range to its first-split-range map */
	// public RangeMap<Double, Integer> orgrange_splitrangid_Map =
	// TreeRangeMap.<Double,Integer> create();

	/* each split-range mapped to its index in arraylist splitrangelist */
	public RangeMap<Double, Integer> splitrange_id_Map = TreeRangeMap
			.<Double, Integer> create();

	public BinarySearchTreeNode() {
	}

	public static final double EFCLONG_DOUBLE = 1e-6;
	
	public void AddRanges(Collection<MyRange> ruleranges) {
		for (MyRange range : ruleranges) {
			splitpointset.add(range.leftbd);
			splitpointset.add(range.rightbd);
		}

		/* make all splitted ranges */
		Double[] splitters = new Double[splitpointset.size()];
		splitpointset.toArray(splitters);
		for (int i = 0; i <= splitters.length; i++) {
			double lb = i > 0 ? splitters[i - 1] : Double.MAX_VALUE * (-1);
			double rb = i < splitters.length ? splitters[i] : Double.MAX_VALUE;
			splitrangelist.add(new SplitRange(lb, rb));
			int splitrangeidx = splitrangelist.size() - 1;
			splitrange_id_Map.put(Range.openClosed(lb, rb), splitrangeidx);
		}

		/* filling up the rangeMap splitrangelist each entry */
		for (MyRange range : ruleranges) {
			double range_lb = range.leftbd + EFCLONG_DOUBLE;
			double range_rb = range.rightbd - EFCLONG_DOUBLE;

			int lb_idx = splitrange_id_Map.get(range_lb);
			int rb_idx = splitrange_id_Map.get(range_rb);

			for (int i = lb_idx; i <= rb_idx; i++) {
				if (splitrangelist.get(i) != null)
					splitrangelist.get(i).addRange(range);
			}
		}
		
//		System.out.println("splitrangelist");
//		System.out.println(new Gson().toJson(splitrangelist));
		
//		for (SplitRange srange : splitrangelist) {
//			if(srange.refranges.size() > 1){
//				System.out.println(new Gson().toJson(srange));
//			}
//		}
		
	}

	public Collection<Integer> getSatisifiedRules(double val) {
		int idx = splitrange_id_Map.get(val);
		return splitrangelist.get(idx).refranges;
	}

//	public static void testRangeMap() {
//		RangeMap<Double, HashSet<Integer>> rangeMap = TreeRangeMap
//				.<Double, HashSet<Integer>> create();
//		HashSet<Integer> s1 = new HashSet<Integer>();
//		s1.add(1);
//		HashSet<Integer> s2 = new HashSet<Integer>();
//		s2.add(2);
//
//		rangeMap.put(Range.closed(1.0, 10.0), s1);
//		System.out.println(rangeMap);
//		rangeMap.put(Range.open(3.0, 6.0), s2);
//		System.out.println(rangeMap);
//
//		HashSet<Integer> val = rangeMap.get(4.0);
//		System.out.println("key=4 " + "val = " + val.toString());
//	}

	public static void functionalTest(){
		BinarySearchTreeNode node = new BinarySearchTreeNode();
		Collection<MyRange> rangelist = new LinkedList<BinarySearchTreeNode.MyRange>();
		rangelist.add(new MyRange(0, 2, 0));
		rangelist.add(new MyRange(1, 3, 1));
		rangelist.add(new MyRange(2, 4, 2));
		node.AddRanges(rangelist);
		
		System.out.println(
				node.getSatisifiedRules(1.5));
	}
	
	
	public static void main(String[] args) {
//		bechmark1();
		functionalTest();

	}

	private static void bechmark1() {
		int[] rulenum_vector = new int[] { 10, 20, 40, 60, 80, 100, 200, 400, 600, 800,
				1000 };
		
		Random rand = new Random();

		for (int i = 0; i < rulenum_vector.length; i++) {

			Collection<MyRange> rangelist = new LinkedList<BinarySearchTreeNode.MyRange>();
			for (int j = 0; j < rulenum_vector[i]; j++) {
				double start = rand.nextDouble() * 500;
				double end = start + rand.nextDouble() * 10;
				rangelist.add(new MyRange(start, end, j));
			}
			BinarySearchTreeNode node = new BinarySearchTreeNode();
			node.AddRanges(rangelist);

			long iter = 0;
			long start = System.currentTimeMillis();
			int hitNum = 0;
			long msgNum = 10000000L;
			double curval = 0.0;
			while (iter < msgNum) {
				curval = rand.nextDouble() * 750;
				hitNum += node.getSatisifiedRules(curval).size();
				iter++;
			}
			
			long end = System.currentTimeMillis();
			System.out
					.println(String
							.format("rule num: %d; use %d ms; hit num: %,d; throughput: %,d rec/s",
									rulenum_vector[i], (end - start), hitNum,
									msgNum * 1000 / (end - start)));

		}
	}
	

}
